package cn.lbd.arithmetic.dp;

public class Knapsack01 {
    public static void main(String[] args) {
        //每个物品的重量
        int[] w = {1, 4, 3, 5, 9, 7, 10};
        //每个物品的价值
        int[] v = {1500, 3000, 2000, 450, 4500, 974, 1200};
        //背包容量
        int m = 12;
        //物品个数
        int n = v.length;
        //dp[i][j]前i个物品中能装入容量为j的背包的最大价值
        int[][] dp = new int[n + 1][m + 1];
        //用于记录最优方案
        int[][] path = new int[n + 1][m + 1];
        //初始化第0列
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        //初始化第0行
        for (int j = 0; j < dp[0].length; j++) {
            dp[0][j] = 0;
        }
        //动态规划求解01背包问题
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (w[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    if (dp[i - 1][j] <= dp[i - 1][j - w[i - 1]] + v[i - 1]) {
                        dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1];
                        path[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }
        //输出动态规划数组
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        //path数组最大行下标
        int i = path.length - 1;
        //path数组最大列下标
        int j = path[0].length - 1;
        //输出最优方案
        while (i > 0 && j > 0) {
            //倒序输出
            if (path[i][j] == 1) {
                System.out.println("第" + i + "个物品放入背包");
                j -= w[i - 1];
            }
            i--;
        }
    }
}
